/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<Interval> ans;
        int n = intervals.size();
        if (n == 0) {
            ans.push_back(newInterval);
        } else if (newInterval.end < intervals[0].start) {
            ans.push_back(newInterval);
            for (int i = 0; i < n; ++i) {
                ans.push_back(intervals[i]);
            }
        } else if (intervals[n - 1].end < newInterval.start) {
            for (int i = 0; i < n; ++i) {
                ans.push_back(intervals[i]);
            }
            ans.push_back(newInterval);
        } else {
            int p0 = 0;
            while (intervals[p0].end < newInterval.start) {
                ++p0;
            }
            int p1 = p0;
            while (p1 < n && intervals[p1].start <= newInterval.end) {
                ++p1;
            }
            Interval t = Interval(min(newInterval.start, intervals[p0].start),
                                  max(newInterval.end, intervals[p1 - 1].end));
            for (int i = 0; i < p0; ++i) {
                ans.push_back(intervals[i]);
            }
            ans.push_back(t);
            for (int i = p1; i < n; ++i) {
                ans.push_back(intervals[i]);
            }
        }
        return ans;

    }
};
